package progect_01;

import java.util.Arrays;

public class test {
	public static void main(String[] args) {
		
		String parentString="BBC ABCDAB ABCDABCDABDE";
		String kidString="ABCDABD";
		int[] next=new int[kidString.length()];
		next=CreNext(kidString);
		for(int i:next) {
			System.out.print(i+" ");
		}
		System.out.println();
		int index=KMP(parentString,kidString, next);
		System.out.printf("在主串的第%d个位置上匹配到了%n",index+1);
		
	}
	
	//KMP算法实现
	public static int KMP(String parent,String kid,int[] next) {
		for(int i=0,j=0;i<parent.length();i++) {
			/*
			 * i-> "BBC ABCDAB ABCDABCDABDE"; 
			 * j->     "ABCDABD";
			 *     
			 *     比如对于这种情况，当i指向指向第二个空格，j指向第二个D的时候，此时不匹配，i不动，
			 *     j就会移动到ABCDAB对应的next数组的部分匹配值的位置，也就是2，然后再继续比较。
			 */
			
			//在第一个位置匹配不到的情况，整体就是主串不后移，只向前移动。
			if(j>0 && parent.charAt(i)!=kid.charAt(j)) {
				//思路:如果匹配不到的话，子串的索引位置就要回到，next数组对应的部分匹配值的位置上。
				j=next[j-1];
			}
			
			//如果第一个字符一样的话就主串子串都移动比较
			if(parent.charAt(i)==kid.charAt(j)) {
				j++;
			}
			if(j==kid.length()) {
				return i-j+1;//之所以+1是因为j比i慢一步
			}
		}
		return -1;
	}
	
	//KMP算法生成next数组
	public static int[] CreNext(String str) {//要匹配的字符串
		int[] next=new int[str.length()];
		int j=0;//前指针
		int i;//后指针
		next[1]=0;//当有一个字符的时候，前后缀的长度都为0
		for(i=1;i<str.length();i++) {
			//考虑不匹配的情况ABCDABD类型的
			//解析：ABCDABD---》生成next数组的时候实际上也采用了Kmp算法的思想，就是i不往后走（<-后）
			//j的位置不断移动，因为如果当j指向C的时候，i指向D会发现此时不匹配了，为了不使用暴力求解法
			//就只移动j的位置
			if(j>0 && str.charAt(i)!=str.charAt(j)) {
				j=next[j-1];
			}
			
			//先考虑AAA类型的
			//     j i
			if(str.charAt(i)==str.charAt(j)) {
				j++;
			}
			next[i]=j;
		}
		return next;
		
	}
	
	
	
}

